package com.demo.java.OD51_100.OD74;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最小传递延迟】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145619872
 */
public class OdMain {
    // 结果初始化为最大值，用于存储最短路径
    public static int result = Integer.MAX_VALUE;
    // 临时变量，用于累加路径的权重
    public static int temp = 0;

    /**
     * 递归方法，用于查找从节点 u 到节点 v 的最短路径
     *
     * @param map     图的邻接表
     * @param u       当前节点
     * @param v       目标节点
     * @param visited 已访问的节点集合，避免循环访问
     */
    public static void find(Map<Integer, Map<Integer, Integer>> map, int u, int v, Set<Integer> visited) {
        Map<Integer, Integer> routesMap = map.get(u); // 获取当前节点 u 的所有邻接节点和边权

        // 遍历 u 的所有邻接节点
        for (Integer key : routesMap.keySet()) {
            // 如果当前节点不是目标节点且没有被访问过
            if (v != key && !visited.contains(key)) {
                // 记录访问的节点
                visited.add(key);
                // 累加路径的权重
                temp += routesMap.get(key);
                // 递归调用，继续寻找从当前节点到目标节点的路径
                find(map, key, v, visited);
            } else if (v == key) {
                // 如果找到了目标节点 v，累加权重
                temp += routesMap.get(key);
                // 更新最短路径的结果
                if (temp != 0) {
                    result = Math.min(result, temp);
                }
                // 重置临时路径权重
                temp = 0;
            }
        }
    }

    public static void main(String[] args) {
        try {
            // 创建扫描器对象，用于读取输入
            Scanner s = new Scanner(System.in);

            // 读取节点数和边数
            String[] spliteValues = s.nextLine().split(" ");
            int n = Integer.parseInt(spliteValues[0]);  // 节点数
            int m = Integer.parseInt(spliteValues[1]);  // 边数

            // 检查节点数是否在合理范围内
            if (n < 1 || n > 100) {
                System.out.println("n data error");
                return;  // 如果不在范围内，输出错误信息并返回
            }

            // 读取每条边的信息
            String[] times = new String[m];
            for (int j = 0; j < m; ++j) {
                times[j] = s.nextLine();
            }

            // 读取最后一行，包含起点 u 和终点 v
            String lastLine = s.nextLine();

            // 使用 TreeMap 创建图的邻接表
            Map<Integer, Map<Integer, Integer>> myMap = new TreeMap<>();

            // 初始化图，所有节点的邻接表为空
            for (int j = 1; j <= n; ++j) {
                HashMap<Integer, Integer> map = new HashMap<>();
                myMap.put(j, map);
            }

            // 构建图，将每条边的信息加入到邻接表中
            for (String time : times) {
                String[] split = time.split(" ");
                int u = Integer.parseInt(split[0]);
                int v = Integer.parseInt(split[1]);
                int w = Integer.parseInt(split[2]);
                myMap.get(u).put(v, w);  // u -> v 边，权重为 w
            }

            // 解析起点和终点
            String[] split = lastLine.split(" ");
            int u = Integer.parseInt(split[0]);
            int v = Integer.parseInt(split[1]);

            // 创建一个集合用于记录已访问的节点，避免重复访问
            Set<Integer> visited = new HashSet<>();
            visited.add(u);  // 将起点加入已访问集合

            // 调用递归方法，开始查找最短路径
            find(myMap, u, v, visited);

            // 如果没有找到路径，返回 -1
            if (Integer.MAX_VALUE == result) {
                result = -1;
            }

            // 输出最终结果
            System.out.println(result);
        } catch (Exception e) {
            // 捕获异常并输出错误信息
            e.printStackTrace();
            System.out.println("input error");
        }
    }
}